Search Results

Documents authored by Arunachalam, Srinivasan

Document
DOI: 10.4230/LIPIcs.TQC.2023.3
Optimal Algorithms for Learning Quantum Phase States

Authors: Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
We analyze the complexity of learning n-qubit quantum phase states. A degree-d phase state is defined as a superposition of all 2ⁿ basis vectors x with amplitudes proportional to (-1)^{f(x)}, where f is a degree-d Boolean polynomial over n variables. We show that the sample complexity of learning an unknown degree-d phase state is Θ(n^d) if we allow separable measurements and Θ(n^{d-1}) if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime poly(n) (for constant d) and is well-suited for near-term demonstrations as it requires only single-qubit measurements in the Pauli X and Z bases. We show similar bounds on the sample complexity for learning generalized phase states with complex-valued amplitudes. We further consider learning phase states when f has sparsity-s, degree-d in its 𝔽₂ representation (with sample complexity O(2^d sn)), f has Fourier-degree-t (with sample complexity O(2^{2t})), and learning quadratic phase states with ε-global depolarizing noise (with sample complexity O(n^{1+ε})). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP circuits.
Cite as

Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. Optimal Algorithms for Learning Quantum Phase States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2023.3,
  author =	{Arunachalam, Srinivasan and Bravyi, Sergey and Dutt, Arkopal and Yoder, Theodore J.},
  title =	{{Optimal Algorithms for Learning Quantum Phase States}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.3},
  URN =		{urn:nbn:de:0030-drops-183139},
  doi =		{10.4230/LIPIcs.TQC.2023.3},
  annote =	{Keywords: Tomography, binary phase states, generalized phase states, IQP circuits}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.25
Trade-Offs Between Entanglement and Communication

Authors: Srinivasan Arunachalam and Uma Girish

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on n bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every k ≥ ~1: Q‖^* versus R2^*: We show that quantum simultaneous protocols with Θ̃(k⁵log³n) qubits of entanglement can exponentially outperform two-way randomized protocols with O(k) qubits of entanglement. This resolves an open problem from [Dmitry Gavinsky, 2008] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gavinsky, 2019; Girish et al., 2022]. R‖^* versus Q‖^*: We show that classical simultaneous protocols with Θ̃(k log n) qubits of entanglement can exponentially outperform quantum simultaneous protocols with O(k) qubits of entanglement, resolving an open question from [Gavinsky et al., 2006; Gavinsky, 2019]. The best result prior to our work was a relational separation against protocols without entanglement [Gavinsky et al., 2006]. R‖^* versus R1^*: We show that classical simultaneous protocols with Θ̃(k log n) qubits of entanglement can exponentially outperform randomized one-way protocols with O(k) qubits of entanglement. Prior to our work, only a relational separation was known [Dmitry Gavinsky, 2008].
Cite as

Srinivasan Arunachalam and Uma Girish. Trade-Offs Between Entanglement and Communication. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.CCC.2023.25,
  author =	{Arunachalam, Srinivasan and Girish, Uma},
  title =	{{Trade-Offs Between Entanglement and Communication}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{25:1--25:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.25},
  URN =		{urn:nbn:de:0030-drops-182957},
  doi =		{10.4230/LIPIcs.CCC.2023.25},
  annote =	{Keywords: quantum, communication complexity, exponential separation, boolean hidden matching, forrelation, xor lemma}
}
Document
DOI: 10.4230/LIPIcs.TQC.2022.3
The Parametrized Complexity of Quantum Verification

Authors: Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, and Bryan O'Gorman

Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)

Abstract
We initiate the study of parameterized complexity of QMA problems in terms of the number of non-Clifford gates in the problem description. We show that for the problem of parameterized quantum circuit satisfiability, there exists a classical algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates but only polynomially with the system size. This result follows from our main result, that for any Clifford + t T-gate quantum circuit satisfiability problem, the search space of optimal witnesses can be reduced to a stabilizer subspace isomorphic to at most t qubits (independent of the system size). Furthermore, we derive new lower bounds on the T-count of circuit satisfiability instances and the T-count of the W-state assuming the classical exponential time hypothesis (ETH). Lastly, we explore the parameterized complexity of the quantum non-identity check problem.
Cite as

Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, and Bryan O'Gorman. The Parametrized Complexity of Quantum Verification. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2022.3,
  author =	{Arunachalam, Srinivasan and Bravyi, Sergey and Nirkhe, Chinmay and O'Gorman, Bryan},
  title =	{{The Parametrized Complexity of Quantum Verification}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-237-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{232},
  editor =	{Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.3},
  URN =		{urn:nbn:de:0030-drops-165104},
  doi =		{10.4230/LIPIcs.TQC.2022.3},
  annote =	{Keywords: parametrized complexity, quantum verification, QMA}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.61
Communication Memento: Memoryless Communication Complexity

Authors: Srinivasan Arunachalam and Supartha Podder

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We study the communication complexity of computing functions F: {0,1}ⁿ × {0,1}ⁿ → {0,1} in the memoryless communication model. Here, Alice is given x ∈ {0,1}ⁿ, Bob is given y ∈ {0,1}ⁿ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x (in particular, her reply is independent of the information from the previous rounds); the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that some of these different variants of our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space-bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study all these space-bounded communication complexity models. We establish the following main results: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose model of computation; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c > 1 for which the memoryless communication complexity is at least c log n? Note that c ≥ 2+ε would imply a Ω(n^{2+ε}) lower bound for general formula size, improving upon the best lower bound by [Nečiporuk, 1966].
Cite as

Srinivasan Arunachalam and Supartha Podder. Communication Memento: Memoryless Communication Complexity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2021.61,
  author =	{Arunachalam, Srinivasan and Podder, Supartha},
  title =	{{Communication Memento: Memoryless Communication Complexity}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{61:1--61:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.61},
  URN =		{urn:nbn:de:0030-drops-136007},
  doi =		{10.4230/LIPIcs.ITCS.2021.61},
  annote =	{Keywords: Communication complexity, space complexity, branching programs, garden-hose model, quantum computing}
}
Document
DOI: 10.4230/LIPIcs.TQC.2020.10
Quantum Coupon Collector

Authors: Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract
We study how efficiently a k-element set S⊆[n] can be learned from a uniform superposition |S> of its elements. One can think of |S>=∑_{i∈S}|i>/√|S| as the quantum version of a uniformly random sample over S, as in the classical analysis of the "coupon collector problem." We show that if k is close to n, then we can learn S using asymptotically fewer quantum samples than random samples. In particular, if there are n-k=O(1) missing elements then O(k) copies of |S> suffice, in contrast to the Θ(k log k) random samples needed by a classical coupon collector. On the other hand, if n-k=Ω(k), then Ω(k log k) quantum samples are necessary. More generally, we give tight bounds on the number of quantum samples needed for every k and n, and we give efficient quantum learning algorithms. We also give tight bounds in the model where we can additionally reflect through |S>. Finally, we relate coupon collection to a known example separating proper and improper PAC learning that turns out to show no separation in the quantum case.
Cite as

Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf. Quantum Coupon Collector. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2020.10,
  author =	{Arunachalam, Srinivasan and Belovs, Aleksandrs and Childs, Andrew M. and Kothari, Robin and Rosmanis, Ansis and de Wolf, Ronald},
  title =	{{Quantum Coupon Collector}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.10},
  URN =		{urn:nbn:de:0030-drops-120692},
  doi =		{10.4230/LIPIcs.TQC.2020.10},
  annote =	{Keywords: Quantum algorithms, Adversary method, Coupon collector, Quantum learning theory}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.45
Improved Bounds on Fourier Entropy and Min-Entropy

Authors: Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Given a Boolean function f:{-1,1}ⁿ→ {-1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each S ⊆ [n] is sampled with probability f̂(S)². The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [E. Friedgut and G. Kalai, 1996] seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C>0 such that ℍ(f̂²)≤ C⋅ Inf(f), where ℍ(f̂²) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f? In this paper we present three new contributions towards the FEI conjecture: ii) Our first contribution shows that ℍ(f̂²) ≤ 2⋅ aUC^⊕(f), where aUC^⊕(f) is the average unambiguous parity-certificate complexity of f. This improves upon several bounds shown by Chakraborty et al. [S. Chakraborty et al., 2016]. We further improve this bound for unambiguous DNFs. iii) We next consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture posed by O'Donnell and others [R. O'Donnell et al., 2011; R. O'Donnell, 2014] which asks if ℍ_{∞}(f̂²) ≤ C⋅ Inf(f), where ℍ_{∞}(f̂²) is the min-entropy of the Fourier distribution. We show ℍ_{∞}(f̂²) ≤ 2⋅?_{min}^⊕(f), where ?_{min}^⊕(f) is the minimum parity certificate complexity of f. We also show that for all ε ≥ 0, we have ℍ_{∞}(f̂²) ≤ 2log (‖f̂‖_{1,ε}/(1-ε)), where ‖f̂‖_{1,ε} is the approximate spectral norm of f. As a corollary, we verify the FMEI conjecture for the class of read-k DNFs (for constant k). iv) Our third contribution is to better understand implications of the FEI conjecture for the structure of polynomials that 1/3-approximate a Boolean function on the Boolean cube. We pose a conjecture: no flat polynomial (whose non-zero Fourier coefficients have the same magnitude) of degree d and sparsity 2^ω(d) can 1/3-approximate a Boolean function. This conjecture is known to be true assuming FEI and we prove the conjecture unconditionally (i.e., without assuming the FEI conjecture) for a class of polynomials. We discuss an intriguing connection between our conjecture and the constant for the Bohnenblust-Hille inequality, which has been extensively studied in functional analysis.
Cite as

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf. Improved Bounds on Fourier Entropy and Min-Entropy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.STACS.2020.45,
  author =	{Arunachalam, Srinivasan and Chakraborty, Sourav and Kouck\'{y}, Michal and Saurabh, Nitin and de Wolf, Ronald},
  title =	{{Improved Bounds on Fourier Entropy and Min-Entropy}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.45},
  URN =		{urn:nbn:de:0030-drops-119062},
  doi =		{10.4230/LIPIcs.STACS.2020.45},
  annote =	{Keywords: Fourier analysis of Boolean functions, FEI conjecture, query complexity, polynomial approximation, approximate degree, certificate complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.16
Two New Results About Quantum Exact Learning

Authors: Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, and Ronald de Wolf

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k-Fourier-sparse n-bit Boolean function from O(k^{1.5}(log k)^2) uniform quantum examples for that function. This improves over the bound of Theta~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Our main tool is an improvement of Chang’s lemma for sparse Boolean functions. Second, we show that if a concept class {C} can be exactly learned using Q quantum membership queries, then it can also be learned using O ({Q^2}/{log Q} * log|C|) classical membership queries. This improves the previous-best simulation result (Servedio-Gortler, SICOMP'04) by a log Q-factor.
Cite as

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, and Ronald de Wolf. Two New Results About Quantum Exact Learning. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.ICALP.2019.16,
  author =	{Arunachalam, Srinivasan and Chakraborty, Sourav and Lee, Troy and Paraashar, Manaswi and de Wolf, Ronald},
  title =	{{Two New Results About Quantum Exact Learning}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.16},
  URN =		{urn:nbn:de:0030-drops-105929},
  doi =		{10.4230/LIPIcs.ICALP.2019.16},
  annote =	{Keywords: quantum computing, exact learning, analysis of Boolean functions, Fourier sparse Boolean functions}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.5
Quantum Hedging in Two-Round Prover-Verifier Interactions

Authors: Srinivasan Arunachalam, Abel Molina, and Vincent Russo

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
We consider the problem of a particular kind of quantum correlation that arises in some two-party games. In these games, one player is presented with a question they must answer, yielding an outcome of either "win" or "lose". Molina and Watrous previously studied such a game that exhibited a perfect form of hedging, where the risk of losing a first game can completely offset the corresponding risk for a second game. This is a non-classical quantum phenomenon, and establishes the impossibility of performing strong error-reduction for quantum interactive proof systems by parallel repetition, unlike for classical interactive proof systems. We take a step in this article towards a better understanding of the hedging phenomenon by giving a complete characterization of when perfect hedging is possible for a natural generalization of the game in the prior work of Molina and Watrous. Exploring in a different direction the subject of quantum hedging, and motivated by implementation concerns regarding loss-tolerance, we also consider a variation of the protocol where the player who receives the question can choose to restart the game rather than return an answer. We show that in this setting there is no possible hedging for any game played with state spaces corresponding to finite-dimensional complex Euclidean spaces.
Cite as

Srinivasan Arunachalam, Abel Molina, and Vincent Russo. Quantum Hedging in Two-Round Prover-Verifier Interactions. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 5:1-5:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2017.5,
  author =	{Arunachalam, Srinivasan and Molina, Abel and Russo, Vincent},
  title =	{{Quantum Hedging in Two-Round Prover-Verifier Interactions}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{5:1--5:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.5},
  URN =		{urn:nbn:de:0030-drops-85782},
  doi =		{10.4230/LIPIcs.TQC.2017.5},
  annote =	{Keywords: prover-verifier interactions, parallel repetition, quantum information}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.3
Quantum Query Algorithms are Completely Bounded Forms

Authors: Srinivasan Arunachalam, Jop Briët, and Carlos Palazuelos

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
We prove a characterization of quantum query algorithms in terms of polynomials satisfying a certain (completely bounded) norm constraint. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. (CCC'16). Using this characterization, we show that many polynomials of degree at least 4 are far from those coming from quantum query algorithms. Our proof is based on a fundamental result of Christensen and Sinclair (J. Funct. Anal., 1987) that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials.
Cite as

Srinivasan Arunachalam, Jop Briët, and Carlos Palazuelos. Quantum Query Algorithms are Completely Bounded Forms. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2018.3,
  author =	{Arunachalam, Srinivasan and Bri\"{e}t, Jop and Palazuelos, Carlos},
  title =	{{Quantum Query Algorithms are Completely Bounded Forms}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{3:1--3:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.3},
  URN =		{urn:nbn:de:0030-drops-83383},
  doi =		{10.4230/LIPIcs.ITCS.2018.3},
  annote =	{Keywords: Quantum query algorithms, operator space theory, polynomial method, approximate degree.}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.25
Optimal Quantum Sample Complexity of Learning Algorithms

Authors: Srinivasan Arunachalam and Ronald de Wolf

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
In learning theory, the VC dimension of a concept class C is the most common way to measure its "richness". A fundamental result says that the number of examples needed to learn an unknown target concept c in C under an unknown distribution D, is tightly determined by the VC dimension d of the concept class C. Specifically, in the PAC model Theta(d/eps + log(1/delta)/eps) examples are necessary and sufficient for a learner to output, with probability 1-delta, a hypothesis h that is eps-close to the target concept c (measured under D). In the related agnostic model, where the samples need not come from a c in C, we know that Theta(d/eps^2 + log(1/delta)/eps^2) examples are necessary and sufficient to output an hypothesis h in C whose error is at most eps worse than the error of the best concept in C. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson, who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio, improved by Zhang, showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is Omega(d^{1-eta}/eps + d + log(1/delta)/eps) for arbitrarily small constant eta>0. Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a log(d/eps) factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the "Pretty Good Measurement" on the quantum state identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class C.
Cite as

Srinivasan Arunachalam and Ronald de Wolf. Optimal Quantum Sample Complexity of Learning Algorithms. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 25:1-25:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.CCC.2017.25,
  author =	{Arunachalam, Srinivasan and de Wolf, Ronald},
  title =	{{Optimal Quantum Sample Complexity of Learning Algorithms}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{25:1--25:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.25},
  URN =		{urn:nbn:de:0030-drops-75241},
  doi =		{10.4230/LIPIcs.CCC.2017.25},
  annote =	{Keywords: Quantum computing, PAC learning, agnostic learning, VC dimension}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.226
On the Robustness of Bucket Brigade Quantum RAM

Authors: Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O'Connor, Michele Mosca, and Priyaa Varshinee Srinivasan

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti, Lloyd, and Maccone [Phys. Rev. Lett., 2008]. Due to a result of Regev and Schiff [ICALP, 2008], we show that for a class of error models the error rate per gate in the bucket brigade quantum memory has to be of order o(2^{-n/2}) (where N=2^n is the size of the memory) whenever the memory is used as an oracle for the quantum searching problem. We conjecture that this is the case for any realistic error model that will be encountered in practice, and that for algorithms with super-polynomially many oracle queries the error rate must be super-polynomially small, which further motivates the need for quantum error correction. We introduce a circuit model for the quantum bucket brigade architecture and argue that quantum error correction for the circuit causes the quantum bucket brigade architecture to lose its primary advantage of a small number of "active" gates, since all components have to be actively error corrected.
Cite as

Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O'Connor, Michele Mosca, and Priyaa Varshinee Srinivasan. On the Robustness of Bucket Brigade Quantum RAM. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 226-244, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2015.226,
  author =	{Arunachalam, Srinivasan and Gheorghiu, Vlad and Jochym-O'Connor, Tomas and Mosca, Michele and Srinivasan, Priyaa Varshinee},
  title =	{{On the Robustness of Bucket Brigade Quantum RAM}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{226--244},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.226},
  URN =		{urn:nbn:de:0030-drops-55594},
  doi =		{10.4230/LIPIcs.TQC.2015.226},
  annote =	{Keywords: Quantum Mechanics, Quantum Memories, Quantum Error Correction}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact